/*
题目: 组合总和Ⅱ
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

https://leetcode.cn/problems/combination-sum-ii
 */
public class CombinationSum2 {
    List< List<Integer> > result = new ArrayList<> ();
    Stack<Integer> path = new Stack<> ();
    int n = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        n = candidates.length;
        Arrays.sort(candidates);
        backTrack(candidates, 0, target);
        return result;
    }

    private void backTrack(int[] candidates, int start, int target) {
        if (start >= n) {
            return ;
        }

        for (int i = start; i < n; i++) {
            int x = candidates[i];
            if (i > start && candidates[i] == candidates[i - 1] || x > target) {
                continue; //去重
            }
            path.push(x);
            if (x == target) {
                result.add(new ArrayList<> (path));
                path.pop();
                continue;
            }

            backTrack(candidates, i + 1, target - x);
            path.pop();
        }
    }
}
